package codetop.microsoft.T79;

/**
 * @Author: 18362
 * @Create: 2022-08-15 17:50:32 星期一
 */
class Solution {
    private boolean isFind;
    private final static int[] dx = new int[] {-1, 1, 0, 0};
    private final static int[] dy = new int[] {0, 0, -1, 1};

    public boolean exist(char[][] board, String word) {
        boolean[][] used = new boolean[board.length][board[0].length];
        for (int i=0; i<board.length; ++i) {
            for (int j=0; j<board[0].length; ++j) {
                dfs(board, used, word, 0, i, j);
                if (isFind)
                    return true;
            }
        }
        return false;
    }

    private void dfs(char[][] board, boolean[][] used, String word, int cur, int x, int y) {
        if (cur == word.length() - 1) {
            if (word.charAt(cur) == board[x][y]) {
                isFind = true;
            }
            return;
        }
        if (isFind)
            return;
        if (word.charAt(cur) != board[x][y])
            return;
        used[x][y] = true;
        for (int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (isValid(board, nx, ny) && !used[nx][ny])
                dfs(board, used, word, cur+1, nx, ny);
        }
        used[x][y] = false;
    }

    private boolean isValid(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length)
            return false;
        return true;
    }
}